解題程式碼

var searchRange = function (nums, target) {
  const binarySearch = (isSearchingLeft) => {
    let l = 0;
    let r = nums.length - 1;
    let index = -1;

    while (l <= r) {
      const mid = Math.floor((l + r) / 2);
      if (nums[mid] > target) {
        r = mid - 1;
      } else if (nums[mid] < target) {
        l = mid + 1;
      } else {
        index = mid;
        if (isSearchingLeft) {
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
    }
    return index;
  };

  return [binarySearch(true), binarySearch(false)];
};

解題思路、演算法

這題的 follow up 要求時間複雜度要是 O(log n)，所以調整一下 binary search 的傳統寫法，

多傳入是往左邊查找或是往右邊查找的 flag，當找到 target 時，還會繼續做 binary search，就能找到在 nums 陣列中，最左和最右的 target 值。

解法的時間、空間複雜度

時間複雜度: O(log n)
空間複雜度: O(1)

參考資料

First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34